package Hard;

import java.util.HashMap;

// Hello.java
public class Scram {
    public static void main(String[] args) {
        String s1 = "great", s2 = "rgeat";
        System.out.println(isScrambleByRecursion(s1, s2));
    }

    /**
     * 1、len = 1 停止 2、a、随机下标，分割s = x + y b、随机操作，交换或者不交换 s = x + y或s = y + x
     * c、分割后的x、y上执行a、b操作直到1停止 3、判断s2是否为s1的扰乱数
     * 
     * @param s1
     * @param s2
     * @return boolean
     */
    public static boolean isScramble(String s1, String s2) {
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        int len1 = s1.length();
        int len2 = s2.length();
        if (len1 != len2)
            return false;

        boolean[][][] dp = new boolean[len1][len1][len1 + 1];// len1 + 1是为了方便dp第三维记录从下标1开始
        // 初始化单个字符的情况
        for (int i = 0; i < len1; ++i) {
            for (int j = 0; j < len1; ++j) {
                dp[i][j][1] = ch1[i] == ch2[j];
            }
        }

        // 枚举区间长度2~n
        for (int len = 2; len <= len1; ++len) {
            // 枚举s1中的起点位置
            for (int i = 0; i <= len1 - len; ++i) {
                // 枚举s2中的起点位置
                for (int j = 0; j <= len1 - len; ++j) {
                    // 枚举划分位置
                    for (int k = 1; k <= len - 1; ++k) {
                        // 第一种情况：s1L -> s2L, s2R -> s2R
                        if (dp[i][j][k] && dp[i + k][j + k][len - k]) {
                            dp[i][j][len] = true;
                            break;
                        }
                        // 第二种情况：s1L -> s2R, s2R -> s2L
                        // s1L起点i，s2R起点j + 前面那段长度len - k, s1R起点i + 前面长度k
                        if (dp[i][j + len - k][k] && dp[i + k][j][len - k]) {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][len1];
    }

    public static boolean isScrambleByRecursion(String s1, String s2) {// 递归的方法，耗时更久
        // 长度不等，必定不能变换
        if (s1.length() != s2.length()) {
            return false;
        }
        // 长度相等，先特判下
        if (s1.equals(s2)) {
            return true;
        }
        // 看一下字符个数是否一致，不同直接return false
        int n = s1.length();
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            map.put(c1, map.getOrDefault(c1, 0) + 1);
            map.put(c2, map.getOrDefault(c2, 0) - 1);
        }
        for (Character key : map.keySet()) {
            if (map.get(key) != 0) {
                return false;
            }
        }

        // 相同的话，开始判断判断，满足一个就能 return true
        for (int i = 1; i < n; i++) {
            boolean flag =
                    // S1 -> T1，S2 -> T2
                    (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i)))
                            ||
                            // S1 -> T2，S2 -> T1
                            (isScramble(s1.substring(0, i), s2.substring(n - i))
                                    && isScramble(s1.substring(i), s2.substring(0, s2.length() - i)));
            if (flag) {
                return true;
            }
        }
        return false;
    }

    public static void myScram(String s) {
        if (s.length() == 1)
            return;
        String[] temp = new String[2];
        for (int i = 1; i < s.length(); ++i) {
            temp = myOperate(s, i);
            for (String temps : temp) {
                System.out.println(temps);
                myScram(s.substring(0, i));
                System.out.println("******");
                myScram(s.substring(i));
            }
        }
    }

    public static String[] myOperate(String s, int index) {
        // 一次a、b操作
        String[] res = new String[2];
        // 不交换
        res[0] = s;
        // 交换
        res[1] = s.substring(index) + s.substring(0, index);
        return res;
    }
}